// 有效的完全平方数
// leetcode 367  问题: 判断一个正整数是否为完全平方数
// https://leetcode.com/problems/valid-perfect-square/
// 方法 1 暴力
var isPerfectSquare = function (num) {
  for (let i = 1; i <= num; i++) {
    if (i ** 2 === num) return true
  }
  return false
}
// 方法 2 二分
var isPerfectSquare = function (num) {
  let l = 0
  let r = num
  while (l <= r) {
    let mid = l + ((r - l) >> 1)
    if (mid < num / mid) {
      l = mid + 1
    } else {
      if (mid === num / mid) return true
      r = mid - 1
    }
  }
  return false
}

// let r = isPerfectSquare(1)

// console.log(r)
// 方法 3 牛顿迭代法
var isPerfectSquare = function (num) {
  let x0 = num
  while (true) {
    let x1 = (x0 + num / x0) / 2
    if (x0 - x1 < 1e-6) break
    x0 = x1
  }

  return parseInt(x0) ** 2 === num
}
// or
var isPerfectSquare = function (num) {
  let x0 = num
  while (true) {
    let x1 = (x0 + num / x0) >> 1
    if (x0 - x1 < 1e-6) break
    x0 = x1
  }
  return x0 ** 2 === num
}
let r = isPerfectSquare(16)

console.log(r)
